import sun.reflect.generics.tree.Tree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-13
 * Time: 22:14
 */
public class SingleList {


    static class TreeNode{
       private int val;
        private TreeNode next;
        public TreeNode(int val){
           this.val = val;
        }
    }
    TreeNode head ;
    //头插
    public void addFirst(int val){
        TreeNode node = new TreeNode(val);
        if(head==null){
            head = node;
            return;
        }
        node.next = head;
        head = node;

    }
    //尾插
    public void addLast(int val){
        TreeNode node = new TreeNode(val);
        if(head==null){
            head = node;
            return;
        }
        TreeNode cur =head;
        while(cur.next !=null ){
            cur =cur.next;
        }
        cur.next = node;

    }
    //头删
    public void deleteFrist(){
        if(head == null){
            System.out.println("单链表为空!");
            return;
        }
        head = head.next;

    }
    //尾删
    public void deleteLast(){
        if(head==null){
            System.out.println("单链表为空!");
            return;
        }
        TreeNode cur = head;
        if(cur.next==null){
            head = null;
            return;
        }
        TreeNode curPrev = null;
        while(cur.next != null){
            curPrev = cur;
            cur = cur.next;
        }
        curPrev.next = null;

    }
//链表节点个数
    public int getSize(){
        TreeNode cur =head ;
        int count = 0;
        while(cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //任意位置插入
    public void insert(int pos ,int val){
        if(pos < 0  || pos > getSize()){
            System.out.println("下标错误!");
            return;
        }
            if(pos == 0){
                addFirst(val);
                return;
            }
            if(pos==getSize()){
                addLast(val);
                return;
            }
            //中间位置插入
        TreeNode cur = head;
            TreeNode node = new TreeNode(val);
            int index = pos;
            while(index-1  != 0){
                cur = cur.next;
                index--;
            }
            node.next = cur.next;
            cur.next = node;
    }


    //查找
    public boolean findVal(int val){
        if(head==null){
            return false;
        }
        TreeNode cur = head;
        while(cur!=null){
            if(cur.val!=val){
                cur= cur.next;
            }else{
                return true;
            }
        }
        return  false;
    }
    //打印
    public void print(){
        TreeNode cur = head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur =cur.next;
        }
        System.out.println();
    }

    /**
     * 删除值为val 的一个节点
     */
    public void remove(int val){
        if(head==null){
            System.out.println("链表为空!");
            return;
        }
        TreeNode cur =head;
        TreeNode curPrev =null;
        while(cur!=null){

            if(cur.val == val){
                if(cur==head){
                    deleteFrist();
                }else{
                    curPrev.next = cur.next;

                }
                return;
            }else{
                curPrev =cur;
                cur =cur.next;
            }
        }

    }

    /**
     * 删除值为val的全部节点
     */
    public void removeAll(int val){
        if(head==null){
            System.out.println("链表为空!");
            return;
        }
        TreeNode cur =head;
        TreeNode curPrev =null;
        while(cur!=null){

            if(cur.val == val){
                if(cur==head){
                    deleteFrist();
                }else{
                    curPrev.next = cur.next;

                }
                cur = cur.next;
            }else{
                curPrev =cur;
                cur =cur.next;
            }
        }

    }
    /**
     * 清空链表
     */
    public void clear(){
        head = null;
    }

    public boolean chkPalindrome() {
        // write code here
        //1.找中间节点
        TreeNode fast = head;
        TreeNode slow = head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //2.翻转
        TreeNode cur = slow.next;
        while(cur!=null){
            TreeNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //3. 判断
        while(head != slow || head.next == slow){
            if(head.val == slow.val){
                head = head.next;
                slow = slow.next;
            }else{
                return false;
            }
        }
        return true;
    }
    public TreeNode partition(int x) {
        // write code here
        if (head == null) {
            return null;
        }
        TreeNode cur = head;
        TreeNode as = null;
        TreeNode ae = null;
        TreeNode bs = null;
        TreeNode be = null;
        while (cur != null) {
            if (cur.val < x) {
                if (as == null) {
                    as = cur;
                    ae = cur;

                } else {
                    ae.next = cur ;
                    ae = cur;
                }
                cur = cur.next;

            } else {
                if (bs == null) {
                    bs = cur;
                    be = cur;

                } else {
                    be.next = cur;
                    be = cur;
                }

                cur = cur.next;
            }
        }
        ae.next= bs;
        return as;
    }
}
